class ListNode {
    int val;
    ListNode next;
    ListNode(int x) { val = x; }
}

class LinkedList {
    ListNode head;  // 头节点

    public boolean checkPalindrome() {
        // 如果链表为空，直接返回false（视需求而定，部分场景可能认为空链表是回文）
        if (head == null) {
            return false;
        }

        // 步骤1：使用快慢指针找到链表的中间节点
        ListNode fastPointer = head; // 快指针，每次移动两步
        ListNode slowPointer = head; // 慢指针，每次移动一步，最终指向中间节点
        while (fastPointer != null && fastPointer.next != null) {
            fastPointer = fastPointer.next.next; // 快指针移动两步
            slowPointer = slowPointer.next;      // 慢指针移动一步
        }

        // 步骤2：反转链表的后半部分
        // 此时 slowPointer 指向中间节点，从它的下一个节点开始反转
        ListNode currentNode = slowPointer.next; // 当前待反转节点
        while (currentNode != null) {
            ListNode nextNode = currentNode.next; // 保存下一个待处理节点
            currentNode.next = slowPointer;       // 反转指针，指向当前节点的前一个节点（slowPointer）
            slowPointer = currentNode;            // slowPointer 前移，成为新的已反转部分的头节点
            currentNode = nextNode;               // currentNode 移动到下一个待处理节点
        }
        // 此时 slowPointer 指向反转后的后半部分的头节点（原链表的尾节点）

        // 步骤3：比较前半部分和反转后的后半部分
        ListNode frontPointer = head;             // 从头节点开始
        ListNode reversedHalfPointer = slowPointer; // 反转后的后半部分的头节点
        while (frontPointer != reversedHalfPointer) { // 当两指针未相遇时继续比较
            // 值不相等，说明不是回文
            if (frontPointer.val != reversedHalfPointer.val) {
                return false;
            }
            // 处理偶数长度链表的提前终止条件（例如 1->2->2->1）
            // 当两指针相邻时，说明已比较完所有节点
            if (frontPointer.next == reversedHalfPointer) {
                return true;
            }
            frontPointer = frontPointer.next;          // 前半部分指针后移
            reversedHalfPointer = reversedHalfPointer.next; // 后半部分指针“前移”（通过反转后的next）
        }

        // 所有节点比较完毕且值相等，是回文
        return true;
    }
}